package com.learn.algorithm;

import java.util.Arrays;

/**
 * 快速排序（左右两边）
 * 快速排序跟冒泡排序一样，都属于交换类排序，通过采用不断的比较和移动元素来实现排序；
 * 快速排序利用了 ”分治法“ 的思想， 通过设置基准数 key ，
 * 将比基准数大的数从前面移动到后面，
 * 比基准数小的数从后面移动到前面，将数组分为两部分，
 * 其中以 key 为中心， key 左边的数比 key 小，key 右边的数比 key 大，
 * 然后对这两部分分别重复这个排序的过程，直到整个有序。
 * 复杂度为：O(nlogn)
 */
public class QuickSort {
    public static void main(String[] args) {
        System.out.println("start...");
        int[] a = {1,2,4,5,7,4,5,3,9,0};
        quickSort(a);
        System.out.println(Arrays.toString(a));
        System.out.println("finish.");
    }

    public static void quickSort(int[] a) {
        if ( a.length > 0 ) {
            quickSort(a,0, a.length-1);
        }
    }

    /**
     * 递归方法
     * @param a
     * @param low
     * @param high
     */
    public static void quickSort(int[] a, int low, int high) {
        //递归算法的出口
        if( low > high ) {
            return;
        }
        int i = low;
        int j = high;
        int key = a[low]; //基准

        //完成一趟排序
        while( i < j ) {
            //从右往左找到第一个小于key的数
            while(i<j && a[j] > key) {
                j--;
            }
            //从左往右找到第一个大于key的数
            while(i<j && a[i] <= key) {
                i++;
            }
            //交换
            if (i < j) {
                int p = a[i];
                a[i] = a[j];
                a[j] = p;
            }
        }
        //调整key的位置
        int p = a[i];
        a[i] = a[low];
        a[low] = p;
        //对key左边的数快排
        quickSort(a, low, i - 1);
        //对key右边的数快排
        quickSort(a, i + 1, high);
    }
}
